//给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
//根节点的引用。 
//
// 一般来说，删除节点可分为两个步骤： 
//
// 
// 首先找到需要删除的节点； 
// 如果找到了，删除它。 
// 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [5,3,6,2,4,null,7], key = 3
//输出：[5,4,6,2,null,null,7]
//解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
//一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
//另一个正确答案是 [5,2,6,null,4,null,7]。
//
//
// 
//
// 示例 2: 
//
// 
//输入: root = [5,3,6,2,4,null,7], key = 0
//输出: [5,3,6,2,4,null,7]
//解释: 二叉树不包含值为 0 的节点
// 
//
// 示例 3: 
//
// 
//输入: root = [], key = 0
//输出: [] 
//
// 
//
// 提示: 
//
// 
// 节点数的范围 [0, 10⁴]. 
// -10⁵ <= Node.val <= 10⁵ 
// 节点值唯一 
// root 是合法的二叉搜索树 
// -10⁵ <= key <= 10⁵ 
// 
//
// 
//
// 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。 
// Related Topics 树 二叉搜索树 二叉树 👍 742 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution450 {
    /**
     * 迭代法
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return root;
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null) {
            if(cur.val == key) break;
            pre = cur;
            if(cur.val > key) cur = cur.left;
            else cur = cur.right;
        }
        if(pre == null){ //删除头节点，或者是树为空
            return deleteNodeOperation(cur);
        }
        if (pre.left != null && pre.left.val == key) { //pre.left!=null是必要的，因为可能不包含key
            pre.left = deleteNodeOperation(cur);
        }
        if (pre.right != null && pre.right.val == key) {
            pre.right = deleteNodeOperation(cur);
        }
        return root;
    }

    private TreeNode deleteNodeOperation(TreeNode cur) {
        if(cur == null) return cur;
        if(cur.right == null) return cur.left;
        //if(cur.left == null) return cur.right; //不需要，下面左右都不为空的处理中已经包含了左空右不空的处理
        TreeNode tmp = cur.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        tmp.left = cur.left;
        return cur.right;
    }


    /**
         * 递归法：有返回值
         * @param root
         * @param key
         * @return
         */
    public TreeNode deleteNode2(TreeNode root, int key) {
        if(root == null) return root;
        if (root.val == key) {
            if (root.left != null && root.right != null) {
                TreeNode temp = root.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                temp.left = root.left;
                root = root.right;
                return root;
            } else {
                return root.left == null ? root.right : root.left;
            }
        }
        if (root.val > key) {
            root.left = deleteNode2(root.left, key);
        }
        if (root.val < key) {
            root.right =  deleteNode2(root.right, key);
        }
        return root;
    }

        /**
         * 递归法：这里用了一个pre指针指向父节点，因为这里的递归没有返回值
         *      可以使用返回值简化代码
         */
    TreeNode pre = null;
    public TreeNode deleteNode1(TreeNode root, int key) {
        if(root == null) return null;
        pre = new TreeNode(root.val);
        TreeNode result = pre;
        pre.left = root; //为了处理删除的是根节点
        traversal(pre.left, key);
//        return pre.left; 错误！！pre也是不断变化的
        return result.left;
    }

    public void traversal(TreeNode cur, int key){
        if(cur == null) return ;
        if (cur.val == key) {
            if(pre.val >= cur.val){ //key位于pre节点的左子树,==对应删除的是根节点
                if (cur.left != null && cur.right != null) { //
                    TreeNode temp = cur.right;
                    while(temp.left != null){
                        temp = temp.left;
                    }
                    temp.left = cur.left;
                    pre.left = cur.right;
                } else {
                    pre.left = cur.left == null ? cur.right : cur.left;
                }
            } else { //key位于pre节点的右子树, 这两部分的逻辑是一样的，可以合在一起写，参考迭代法
                if(cur.left != null && cur.right != null){
                    TreeNode temp = cur.right;
                    while(temp.left != null){
                        temp = temp.left;
                    }
                    temp.left = cur.left;
                    pre.right = cur.right;
                } else {
                    pre.right = cur.left == null ? cur.right : cur.left;
                }
            }
            return ;
        }
        pre = cur;
        if(cur.val > key){
            traversal(cur.left, key);
        }
        if (cur.val < key) {
            traversal(cur.right, key);
        }
    }

//    public static void main(String[] args) {
//        Integer[] arr = new Integer[]{5,3,6,2,4,null,7};
//        TreeNode root = BinaryTreeFactory.generateBinaryTreeFromArray(arr);
//        TreeNode treeNode = new Solution().deleteNode(root, 5);
//    }
}
//leetcode submit region end(Prohibit modification and deletion)
